package com.ting.test.algorithms.stack;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 利用普通队列实现栈
 * 单端队列
 * 栈:
 * 先进后出 头进头出
 */
public class 用队列实现栈 {

    public static void main(String[] args) {
        int[] arr = new int[]{11, 2, 4, 6, 8, 9, 0, 6};
        MyStack stack = new MyStack(arr.length);
        for (int s : arr) {
            boolean push = stack.push(s);
            System.out.println("push:" + s + "," + push);
        }

        for (int s : arr) {
            Integer pop = stack.pop();
            System.out.println("pop:" + pop);
        }
    }


    static class MyStack {
        Queue<Integer> pushQueue;
        Queue<Integer> popQueue;


        public MyStack(int size) {
            this.popQueue = new LinkedList();
            this.pushQueue = new LinkedList();
        }

        public boolean push(int param) {
            pushQueue.offer(param);
            return true;
        }

        /**
         * 当pop中有数据时，直接pop
         * 当pop为空时 将push中的数据全部倒入pop中
         *
         * @return
         */
        public Integer pop() {
            while (pushQueue.size() > 1) {
                popQueue.offer(pushQueue.poll());
            }

            Integer ans = null;
            if (pushQueue.size() == 1) {
                ans = pushQueue.poll();
            }
            Queue temp = pushQueue;
            pushQueue = popQueue;
            popQueue = temp;

//            swap(popQueue, pushQueue);
            return ans;
        }

        public void swap(Queue queue1, Queue queue2) {
            Queue temp = queue1;
            queue1 = queue2;
            queue2 = temp;
        }

        /**
         * 当pop中有数据时，直接pop
         * 当pop为空时 将push中的数据全部倒入pop中
         *
         * @return
         */
        public Integer peek() {
            while (pushQueue.size() > 1) {
                popQueue.offer(pushQueue.poll());
            }

            if (pushQueue.size() == 1) {
                int ans = pushQueue.poll();
                popQueue.offer(ans);
                return ans;
            }
            swap(popQueue, pushQueue);
            Queue temp = pushQueue;
            pushQueue = popQueue;
            popQueue = temp;
            return null;
        }
    }
}
